package 二分搜索入门;

import java.util.Arrays;

/**
 * @author 冷加宝
 * @version 1.0
 */
public class Binary_Search {

    public static void main(String[] args) {
        int N = 200;
        int V = 1000;
        int testTimes = 5000;
        System.out.println("测试开始");
        for(int i = 0; i < testTimes; i++){
            int n = (int) (Math.random() * N);
            int[] arr = randomArray(n, V);
            Arrays.sort(arr);
            int target = (int)(Math.random() * V);
            if(exist(arr, target) != right(arr, target)){
                System.out.println("出错了");
            }
        }
        System.out.println("测试结束");
    }

    public static int[] randomArray(int n, int v){
        int[] arr = new int[n];
        for(int i = 0; i < n; i++){
            arr[i] = (int)(Math.random() * v + 1);
        }
        return arr;
    }

    public static boolean right(int[] arr, int target){
        for (int cur : arr) {
            if(cur == target){
                return true;
            }
        }
        return false;
    }

//    前提数组有序,在有序数组中确定target存在还是不存在
    public static boolean exist(int[] arr, int target){
        if(arr == null || arr.length == 0){
            return false;
        }
        int left = 0, right = arr.length-1, mid = 0;
        while(left<=right){
            mid = left + ((right - left) >> 1);
            if(arr[mid] == target){
                return true;
            }else if(arr[mid] < target){
                left = mid + 1;
            }else if(arr[mid] > target){
                right = mid - 1;
            }
        }
        return false;
    }

//    在有序数组中找>=target的最左位置
    public static int findLeft(int[] arr, int target){
        if(arr == null || arr.length == 0){
            return -1;
        }
        int left = 0, right = arr.length-1, mid = 0;
        int ans = -1;
        while(left <= right){
            mid = left + ((right-left)>>1);
            if(arr[mid] >= target){
                ans = mid;
                right = mid - 1;
            }else{
                left = mid + 1;
            }
        }
        return ans;
    }

//   在有序数组中找<=target的最右位置
    public static int findRight(int[] arr, int target){
        if(arr == null || arr.length == 0){
            return -1;
        }
        int left = 0, right = arr.length-1, mid = 0;
        int ans = -1;
        while(left <= right){
            if(arr[mid] <= target){
                ans = mid;
                left = mid + 1;
            }else{
                right = mid - 1;
            }
        }
        return ans;
    }

//    二分搜索不一定发生在有序数组上（比如寻找峰值问题）
// 峰值元素是指其值严格大于左右相邻值的元素
// 给你一个整数数组 nums，已知任何两个相邻的值都不相等
// 找到峰值元素并返回其索引
// 数组可能包含多个峰值，在这种情况下，返回 任何一个峰值 所在位置即可。
// 你可以假设 nums[-1] = nums[n] = 无穷小
// 你必须实现时间复杂度为 O(log n) 的算法来解决此问题。
    public static int findPeakElement(int[] arr){
        if(arr == null || arr.length == 0){
            return -1;
        }
        int n = arr.length;
        if(n == 1){
            return 0;
        }
        if(arr[0] > arr[1]){
            return 0;
        }
        if(arr[n-1] > arr[n-2]){
            return n-1;
        }
        int left = 1, right = n-2, mid = 0;
        int ans = -1;
        while(left <= right){
            mid = left + ((right-left)>>1);
            if(arr[mid-1] > arr[mid]){
                right = mid-1;
            }else if(arr[mid] < arr[mid+1]){
                left = mid +1;
            }else{
                ans = mid;
                break;
            }
        }
        return ans;
    }
}
